// 给定一个未排序的整数数组nums和一个整数k，返回数组中第k个最大的元素

// 思路1，利用堆排序的特性，构建大顶堆，可以确定一个最大的元素，我们可以寻找k - 1次，那么数组首位就是第k大的元素
// 时间复杂度：O(nlogn)
// 空间复杂度：O(1)

function findKthLargest(arr, k) {
    function buildMaxHeap(arr) {
        for (let i = Math.floor((arr.length - 2) / 2); i >= 0; i--) {
            heapify(arr, i, arr.length - 1)
        }
    }
    function heapify(arr, start, end) {
        let left = 2 * start + 1
        let right = left + 1
        while (left <= end) {
            let maxIndex = start
            if (arr[left] > arr[maxIndex]) {
                maxIndex = left
            }
            if (right <= end && arr[right] > arr[maxIndex]) {
                maxIndex = right
            }
            if (maxIndex === start) {
                break
            }
            [arr[maxIndex], arr[start]] = [arr[start], arr[maxIndex]];
            start = maxIndex
            left = 2 * start + 1
            right = left + 1
        } 
    }
    buildMaxHeap(arr)
    for (let i = 0; i < k - 1; i++) {
        [arr[0], arr[arr.length - i - 1]] = [arr[arr.length - i - 1], arr[0]];
        heapify(arr, 0, arr.length - i - 2)        
    }
    return arr[0]
}

let arr = [3, 2, 1, 5, 6, 4]
let k = 2
console.log(findKthLargest(arr, k));

// 思路2，利用快排思路，每轮快排都会确定一个元素的位置，我们只需要判断这个位置是否符合要求就可以返回对应的值
// 时间复杂度：最好Onlogn，最坏On2，平局Onlogn
// 空间复杂度：最好Ologn(递归栈深度)，最坏On
function findKthLargest2(arr, k) {
    function quickSort(arr, left, right, k) {
        if (left < right) {
            let index = partition(arr, left, right)
            if (arr.length - index === k) {
                console.log('index', index)
                console.log(arr)
                return arr[index]
            } else if (arr.length - index < k) {
                return quickSort(arr, left, index - 1, k)
            } else {
                return quickSort(arr, index + 1, right, k)
            }
        }
        // 注意这里的返回值
        return arr[arr.length - k]
    }
    function partition(arr, left, right) {
        let pivot = Math.floor(Math.random() * (right - left)) + left
        let pivotVal = arr[pivot];
        [arr[left], arr[pivot]] = [arr[pivot], arr[left]];
        // i的左侧都是小于pivotVal的元素
        let i = left + 1
        // 这里注意是小于等于
        for (let j = i; j <= right; j++) {
            if (arr[j] < pivotVal) {
                [arr[i], arr[j]] = [arr[j], arr[i]];
                i++
            }
        }
        [arr[left], arr[i - 1]] = [arr[i - 1], arr[left]];
        return i - 1
    }
    return quickSort(arr, 0, arr.length - 1 , k)
}

let arr1 = [3,2,1,5,6,4]
let k1 = 2
console.log(findKthLargest2(arr1, k1));